闲话:这场做出ACD可以到前百名.
原题链接:Codeforces 1384 D
题目大意:有两个人初始分数都是,一共有个值.每一步操作可以让自己的分数和其中任意一个异或起来,并删掉这个.最后两边谁的值更大谁获胜.问先手是否必胜,或是平局.
数据范围:
先把特殊情况抠掉:平局的时候两边的分数是相等的,因为两边的分数就是取两个不同的集合,整个集合的并集是原来的序列,交集是空集,所以两边的分数异或起来是说明整个序列的异或和为.因此整个序列异或和的时候,游戏为平局.
如果不为.因为整个应该是两个数的异或和,即两边的分数的异或和,那么的某一位如果是的话代表着有一边是而有一边是,也就是说,两边的分数在这一位上出现了不同,这一位就是决定了两边的分数谁更大的关键位置.假设这一位是,满足x >> i & 1这个表达式为真.显然两边的分数在这一位上是各取了原先序列里所有的数这一位上的数位值,再异或起来得到的(因为异或是不进位的,本位的值与其他位的元素无关),所以这一位上到底是先手分的还是后手的分到应该要看整个序列里的所有元素这一位上具体是多少.显然只有两种取值或,分别记为和.
多种情况,一个一个来分析:
①如果是偶数.
由于本位置上异或和应该是,所以与之矛盾了,因为偶数个必然组成,而之后再有多少个都不会让结果变得更大,因此这个情况其实是矛盾的.
②如果是奇数
在这个情况下,的数量其实是有很大影响的,通过枚举可以发现,如果是奇数个的话,实际上是有两种情况的:因为在有的倍数个和单个的的时候,组合起来的异或值还是,但是如果去掉的倍数的部分之后,余的是个,这个时候就会造成一个的情况,他们的异或和是.这里要继续划分情况讨论.
1'如果即余下只有一个的情况.
在这种情形下,对于我这个先手的人来说,我只需要先拿掉一个,那么接下来我要得到一个异或和是的方案,接下来对手怎么做我就怎么做,这样的话,我手上是必然得到奇数个和若干个个的,这样结束之后,我手上偶数个得到的就是,最后多一个,我就胜利了.
也就是说在1'这个情形下,先手是必胜的,因为他可以抢掉奇数的那一个.
2'如果即余下是有三个的情况.
这种情况可能就难看了一些,因为他是余下了三个.作为先手,还是按之前的策略来抢出一个奇数的,但是此时后手完全可以仿照先手的镜像操作,来使先手得到偶数个的.不过这一点不是总能实现的:假设当的个数是偶数的时候,由于是偶数,所以整个操作序列里可以把偶数的的部分全部删去,只看留下的的操作:既然是余数是,那么整个局面除了的倍数的部分,一定是一个的序列,即先手必然取到偶数个导致手上是.也就是说如果,此时就是必胜的.不过另外一种情况,也就是当的个数也是奇数的时候,会补齐操作序列里的数量,就是说此时局面又可以等价成这个情况,那么我先手选择掉的话,就可以做到必胜.此时对于先手来说又是一个必胜的.
综上,整个局面当且仅当且时后手必胜,其余情况先手必胜.
以上都是我的个人的思考过程,想通了之后,这个问题可以用抵消的考虑方式快速的得到结论,下面说明一下:
首先,偶数个或者偶数个必然得到,对结果是没有影响的,所以局面可以等价的把他们删掉.因此第一种情况是完全不需要考虑的.
其次第二种情况里,也就是说是奇数的时候的时候,又有两种情况了:因为对于奇数情况来说,如果模余,得到的是,如果得到的是,则是.为什么会有这个问题?可以按消去的想法简单的想一下,就是说偶数的部分虽然是可以消掉的,但是不一定是完全能消的,比如在的前提下,如果是偶数个,则偶数个很显然是可以消掉而毫无影响,但是不行,因为偶数个消掉之后,先手的人在这里必然会拿到两个,而不能直接按消去的办法直接把他变成.从另外一个角度来说明,是奇数,但是也要看他去掉之后有几个一对,这里面有几对额外的一对,决定了他最后是还是.这一点需要特别注意.在这之后第二种情况下就分别对应和两种情况了,情形简化之后就很好考虑了.剩下的实现也比较简单,就不多提了.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;cin >> T;
while(T--)
{
int n;cin >> n;
int xs = 0;
vector<int> a(n);
for (auto &i : a)
{
cin >> i;
xs ^= i;
}
if(!xs) cout << "DRAW\n";
else
{
for(int i = 31;i >= 0;--i)
{
int ch = xs >> i & 1;
if(!ch) continue;
int c1 = 0,c0 = 0;
for(auto& v : a)
{
if(v >> i & 1) ++c1;
else ++c0;
}
if(c1 % 4 == 3 && c0 % 2 == 0) cout << "LOSE\n";
else cout << "WIN\n";
break;
}
}
}
return 0;
}